'''
https://leetcode.cn/problems/intersection-of-two-linked-lists/
'''
from typing import Optional

from c03_list.utils import ListNode


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        n1 = n2 = 0
        t1, t2 = headA, headB
        while t1.next:
            n1 += 1
            t1 = t1.next
        while t2.next:
            n2 += 1
            t2 = t2.next
        if t1 != t2: return None
        t1, t2 = headA, headB
        if n1 > n2:
            for _ in range(n1 - n2):
                t1 = t1.next
        else :
            for _ in range(n2 - n1):
                t2 = t2.next
        while t1:
            if t1 == t2:
                return t1
            t1, t2 = t1.next, t2.next
        return None



    def getIntersectionNode_2(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        dict = set()
        cur = headA
        while cur:
            dict.add(cur)
            cur = cur.next
        cur = headB
        while cur:
            if cur in dict:
                return cur
            cur = cur.next
        return None